Q: The relationship of skew heaps to leftist heaps is analogous to that of?
Solution: Splay tree is a self -adjusting version of AVL tree. Similarly, skew heap is a self-adjusting version of leftist heap.
Q: What is the fundamental operation performed in skew heaps?
Solution: The fundamental operation of skew heaps is merging. Hence, it is similar to that of a leftist heap.
Q: What is the time per operation of merging, insertion and deletion operations in a skew heap?
Solution: Skew heaps support merging, insertion and deletion all effectively in O(log N) time per operation.
Q: Why would a recursive implementation fail in skew heaps?
Solution: In skew heaps, a recursive implementation could fail because of lack of stack space even though performance is acceptable.
Q: Which of the following is difficult to determine the right path length?
Solution: It is an open problem to determine precisely the expected right path length of both leftist and skew heaps and comparatively, the latter is difficult.
Q: The worst case analysis for a naïve merge is given as?
Solution: The worst-case analysis for the naïve merge is an insertion in a right heavy tree. So, insertion takes O(N).
Q: How many types of the merge are available in skew heaps?
Solution: Two kinds of the merge are available in skew heaps- naïve merge and skew merge.
Q: Naïve merge cannot be done in a skew merge.
Solution: One way of doing skew merge is to begin with naïve merge and then swapping the left and right children of the tree.
Q: What is the amortized efficiency of skew merge?
Solution: The amortized efficiency of a skew heap is mathematically found to be O( log N).
Q: In skew heaps, certain constraints are to be met in order to perform swapping.
Solution: In skew heaps, swaps are unconditional. It is done with the exception that the largest of all nodes does not have its children swapped.
| You Have Score | /10 |